package LeetCode刷题;

import java.util.Scanner;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-22 20:28
 * @description: Functions of this class is
 **/
public class NoNo动态规划编辑距离 {
    //编辑距离
    private static String s1;
    private static String s2;
    private static int k=1;
    public static void main(String args[]){
        Scanner scanner=new Scanner(System.in);
        System.out.println("请依次输入两个字符：");
        s1=scanner.next();
        s2=scanner.next();
        int d[][]=new int[s1.length()+1][s2.length()+1];
        System.out.println("两个字符之间的最短编辑距离为："+edit(d));
        System.out.println("其最优解的步骤之一为：");
        pathPrint(d,s1.length(),s2.length());//从最后开始往回打印
    }
    private static int edit(int d[][]){
        int len1=s1.length();
        int len2=s2.length();
        //先对矩阵进行初始化
        //为什么要初始化为对应的索引号值呢，首先要搞清楚dp[i][j]的意义，他的意义就是从i转换到j所需要的最少的步骤数字
        //所以下面的初始化就是要算出0~i之间的小步数即为i、0~j之间的最少步数即为j
        for(int i=0;i<=len1;i++){
            d[i][0]=i;
        }
        for(int j=0;j<=len2;j++){
            d[0][j]=j;
        }

        for(int i=1;i<=len1;i++){//从1索引号开始，防止后面的i-1越界了
            for(int j=1;j<=len2;j++){
                int diff;//定义一个参数记录当s1与s2当前比较到的字符是相等还是不相等
                if(s1.charAt(i-1)==s2.charAt(j-1)){//从1开始比较，减去一表示比较的是当前这个字符
                    diff=0;
                }
                else{
                    diff=1;
                }
                d[i][j]=Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]+diff);
                //d[i-1][j]+1为删除了一个元素，即将待删除元素前面所计算到的编辑距离价值+1即可
                //d[i][j-1]+1为插入一个元素，即将被插入元素之前所计算到的编辑距离价值+1即可
                //d[i-1][j-1]+diff为当前匹配到的字符长度与另一字符当前匹配到的长度相同，然后第一个字符中的一个字符要被另一个字符串中的一个字符替换掉或者就不替换，这取决于当前两字符是否相等
            }
        }
        return d[len1][len2];//返回两个字符串长度为索引号所在的值，即为其最短编辑距离
    }

    /**
     *
     * @param i 当前打印路径起始点横坐标
     * @param j 当前打印路径起始点纵坐标
     */
    private static void pathPrint(int d[][],int i,int j){
        if(i==0||j==0){//说明已经修改完成了,直接返回了
            return;
        }
        else{
            if(s1.charAt(i-1)==s2.charAt(j-1)){
                pathPrint(d,i-1,j-1);//说明当前s1与s2的字符是相等的，直接回退即可
            }
            else if(d[i][j]==d[i-1][j]+1){//说明当前字符经历了删除字符的过程
                pathPrint(d,i-1,j);//先回退后输出，这样才可以倒序输出
                System.out.println("第"+(k++)+"步删除了字符"+s1.charAt(i-1));
            }
            else if(d[i][j]==d[i][j-1]+1){
                pathPrint(d,i,j-1);//先回退后输出，这样才可以倒序输出
                System.out.println("第"+(k++)+"步插入字符"+s2.charAt(j-1));
            }
            else{
                pathPrint(d,i-1,j-1);//先回退后输出，这样才可以倒序输出
                System.out.println("第"+(k++)+"步将字符替换成"+s1.charAt(i-1)+"替换成"+s2.charAt(j-1));
            }
        }
    }
}